package cxydmmszl.chapter08.t144;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 加油站良好出发点问题
 * <li style="color: green;">Desc</li>
 * N 个加油站组成一个环形，给定两个长度都是 N 的非负数组 oil 和 dis(N>1)，
 * oil[i] 代表第 i 个加油站存的油可以跑多少千米，
 * dis[i] 代表第 i 个加油站到环中下一个加油站相隔多少千米。<br/>
 * 假设你有一辆油箱足够大的车，初始时车里没有油。
 * 如果车从第 i 个加油站出发，最终可以回到这个加油站，那么第 i 个加油站就算良好出发点，否则就不算。
 * 请返回长度为 N 的 boolean 型数组 res，res[i] 代表第 i 个加油站是不是良好出发点。<br/>
 * <b>规定只能按照顺时针走，也就是 i 只能走到 i+1 ，N 只能走到 1。</b>
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(n)，空间复杂度为 O(1)
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * 0⩽oil[i], dis[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N 表示加油站数量。
 * 第二行 N 个整数，表示 oil 数组。
 * 第三行 N 个整数，表示 dis 数组。
 * <li style="color: green;">Output</li>
 * 输出 N 个整数。若第 i 个整数为 0 表示该位置不是良好出发点，
 * 为 1 表示该位置是良好出发点。
 * <li style="color: blue;">Link</li> CD53
 *
 * @author habitplus
 * @since 2021-10-15 16:14
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException("Input is valid!");
        }
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] oil = new int[n];
        int[] dis = new int[n];
        for (int i = 0; i < n; i++) oil[i] = nextInt();
        for (int i = 0; i < n; i++) dis[i] = nextInt();

        boolean[] ans = goodStartPoint2(oil, dis);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            sb.append(ans[i] ? 1 : 0).append(' ');
        }
        System.out.println(sb.toString());
    }

    /*
        简单模拟：O(N^2)
     */
    private static boolean[] goodStartPoint1(int[] oil, int[] dis) {
        if (oil == null || dis == null || oil.length == 0 || dis.length != oil.length)
            return new boolean[0];

        if (oil.length == 1) return new boolean[]{true};

        int n = oil.length;
        boolean[] good = new boolean[n];

        int rest, j;
        for (int i = 0; i < n; i++) {
            rest = oil[i];
            j = i;
            do {
                if (rest >= dis[j]) {
                    rest -= dis[j];
                    j = (j + 1) % n;
                    rest += oil[j];
                } else {
                    j = -1;
                    break;
                }
            } while (j != i);

            if (j == i) good[i] = true;

        }

        return good;
    }

    /*
        解法二：O(N)
     */
    public static boolean[] goodStartPoint2(int[] oil, int[] dis) {
        if (oil == null || dis == null || oil.length < 2 || oil.length != dis.length) {
            return null;
        }

        // 更改 dis 数组，即 dis[i] = oil[i] - dis[i]，
        // 获得 init 出发点：这个点必须是 oil[i] - dis[i] >= 0 的点，可能存在多个这样的点，任意返回其中一个即可
        int init = changeDisArrayGetInit(dis, oil);

        return init == -1 ? new boolean[oil.length] : enlargeArea(dis, init);
    }

    private static boolean[] enlargeArea(int[] dis, int init) {
        int n = dis.length;
        boolean[] res = new boolean[n];
        int start = init;
        int end = nextIndex(start, n);
        long need = 0, rest = 0;
        do {
            // 当前来到的 start 已经在连通区域中，可以确定后续的开始点一定无法转完一圈
            if (start != init && start == lastIndex(end, n)) {
                break;
            }

            // 当前来到的 start 不再连通区域中，就扩充连通区域
            if (dis[start] < need) {
                // 从当前 start 出发，无法到达 init 点
                need -= dis[start];
            } else {
                // 如果 start 可以到达 init 点，扩充连通区域的结束点
                rest += dis[start] - need;
                need = 0;
                while (rest >= 0 && end != start) {
                    rest += dis[end];
                    end = nextIndex(end, n);
                }

                // 如果连通区域已经覆盖整个环，当前 start 是良好的出发点，进入 2 阶段
                if (rest >= 0) {
                    res[start] = true;
                    connectGood(dis, lastIndex(start, n), init, res);
                    break;
                }
            }
            start = lastIndex(start, n);
        } while (start != init);

        return res;
    }

    /*
        已知 start 的 next 方向上有一个良好的出发点，
        start 如果可以达到这个良好出发点，那么从 start 出发一定可以转一圈
     */
    private static void connectGood(int[] dis, int start, int init, boolean[] res) {
        int n = dis.length;
        long need = 0;
        while (start != init) {
            if (dis[start] < need) {
                need -= dis[start];
            } else {
                res[start] = true;
                need = 0;
            }
            start = lastIndex(start, n);
        }
    }

    private static int lastIndex(int i, int n) {
        return i == 0 ? (n - 1) : (i - 1);
    }

    private static int nextIndex(int i, int n) {
        return i == n - 1 ? 0 : (i + 1);
    }

    private static int changeDisArrayGetInit(int[] dis, int[] oil) {
        int init = -1;
        for (int i = 0; i < dis.length; i++) {
            dis[i] = oil[i] - dis[i];

            if (dis[i] >= 0) {
                // 返回最后一个 dis[i] >= 0 的点
                init = i;
            }
        }
        return init;
    }
}
